import numpy as np

m=5 #钱数
f = np.array([[0, 11, 12, 13, 14, 15],
              [0, 0, 5, 10, 15, 20],
              [0, 2, 10, 30, 32, 40],
              [0, 20, 21, 22, 23, 24]]) #效益
p=np.zeros(len(f))  #方案

## 初始化
x = np.array(list(range(m+1)))
F = np.zeros((len(f), len(x)))
X = np.zeros((len(f), len(x)))

## 求解
F[0] = f[0]
X[0] = x
for j in range(1, len(f)):
    for i in range(len(x)):
        fi = f[j, :i+1]+F[j-1, :i+1][::-1]
        F[j, i] = np.max(fi)
        X[j, i] = X[0, np.where(fi == np.max(fi))]

## 追溯
mm=m
for i in range(len(F)-1,-1,-1):
    p[i]=X[i, mm]
    mm -= int(X[i, mm])

print("F矩阵：")
print(F)
print("X矩阵：")
print(X)
print("分配方案：",p)
print("最大效益：",F[len(F)-1, m])